Черч-Тјурингова теза

У теорији израчунљивости, Черч-Тјурингова теза (такође позната као Тјуринг-Черчова теза, Черч-Тјурингове претпоставке, Черчова теза, Черчова претпоставка и Тјурингова теза) је хипотеза ("теза") о природи израчунљивих функција. Једноставно речено, Черч-Тјурингова теза гласи да је функција на природним бројевима израчунљива у неформалном смислу (тј израчунљива од стране људског бића коришћењем метода оловке и папира, игноришући ограничења ресурса) ако и само ако је израчунљива Тјуринговом машином. Теза је добила име по америчком математичару Алонзу Черчу и британском математичару Алану Тјурингу.

Пре прецизног дефинисања израчунљивих функција, математичари често користе неформалан термин ефективно израчунљив да опишу функције које су за израчунљиве методама папира и оловке-. 1930-их, било је неколико независних покушаја да се формализује појам Израчунљивости:

• 1933, Аустријски-Амерички математичар Курт Гедел, са Жаком Ербраном, је направио дормалну дефиницију класа под називом општа рекурзивна функција. Класа општих рекурзивних функција је најмања класа функција (могуће са више од једног аргумента) која укључује константне функције, пројекте, функцију наследног, и који је затворен у сложеној функцији и рекурзији.
• 1936, Алонзо Черч је створио метод за дефинисање функција под називом Ламбда рачун. У оквиру ламбда рачуна он је дефинисао кодирање природних бројева под називом Черчови бројеви. Функција над природним бројевима се зове ламбда израчунљива ако се одговарајућа функција на Черчовим бројевима може представити у тајању ламбда рачуна.
• Такође 1936, пре проучавања Черчовог рада, Алан Тјуринг је створио теоретски модел за машине, који се сада зове Тјурингове машине, које се могу побринути за рачунање из улаза манипулацијом симбола на траци. С обзиром на одговарајуће кодирање природних бројева као секвенце симбола, функција природних бројева  се назива Тјуринг израчунљива ако неке Тјурингове машине израчунају одговарајућу функцију над кодираним природним бројевима.

Черч и Тјуринг су доказали да се ове три формално дефинисане класе израчунљивих функција поклапају: функција је ламбда израчуљива  ако и само ако је Тјуринг израчунљива и акко је опште рекурзивна. Ово је натерало математичаре и информатичаре да поверују да је концепт израчунљивости тачно окарактерисан овим трома еквивалентним процесима. Остали формални покушаји да се карактерише израчунљивост је касније ојачао снагу овог веровања (погледати испод).

С друге стране, Черч-Тјурингова теза наводи да су горенаведене три формално дефинисане класе израчинљивих функција поклапају са неформалном појмом ефикасно прорачунљиве функције. Пошто, као неформални појам, концепт ефективне предвидивости нема формалну дефиницију, теза, иако има скоро универзалну прихваћеност, не може бити формално доказана.

Од свог оснивања, варијације на основној тези су се појавиле, укључујући изјаве о томе шта ће моћи физички бити реализовано уз помоћ рачунара у нашем универзуму (физичка Черч-Тјуринг теза) и шта ће моћи бити ефикасно израчунато (Сложеност-теоријски Черч-Тјурингова теза). Ове варијације нису због Черча или Тјуринга, али проистичу из каснијег рада у теорији сложености и дигиталне физике. Теза има импликације за филозофију духа.

Искази у Черчовим и Тјуринговим речима

Џ. Б. Росер (1939) бави се појмом "ефективне израчунљивости" на следећи начин: "Јасно постојање ЦЦ и РЦ (Черчови је и Росерови докази) претпоставља прецизну дефиницију 'ефективног' 'Ефективни метод" се овде користи у веома посебном смислу методе сви кораци који су прецизно унапред одређени и који сигурно произведе одговор у коначном броју корака. „Такосе прилог-придев "ефективан"  користи у смислу "1А: производећи одлучујућег, убедљивог, или жељеног ефекта" и "способан да произведе резултат".

У наставку, речи "ефикасно израчунљив" ће значити "произведен од стране било ког интуитивног 'ефективног' значи уопште" и "ефективно подложан рачунању" ће значити "произведени од стране Тјурингове-машине или еквивалентног механичког уређаја". Тјурингова "дефиниција" дата у фусноти у својој 1939. докторирао тезу Системи логике базираних на редним бројевима под надзором Черча, су готово исти:

"† Ми ћемо користити израз" израчунљива функција ' да означимо функцију израчунату на машини, и пустимо ' ефективно израчунате 'да се односи на интуитивну идеју без посебне  идентификације са било којим од ових дефиниција. "

Теза може гласити као следеће:

Свака ефективно израчунљива функција је функција подлежна рачунању.

Тјуринг је то изјавио на овај начин:

"Констатовано је да је ..." функција је ефективно израчунљива ако се њене вредности могу наћи помоћу неког чисто механичког процеса. " Можемо узети дословно, схватајући да је чисто механички процес онај који може да се обавља помоћу машине ... доводи до ... идентификације израчунљивости † са ефективном предвидивошчу. "(† је фуснота изнад, Ибид.)

Историја

Један од важних проблема за логичаре 1930. био је Давид Хилбертов Entscheidungsproblem, која је затражила да ли је механички поступак за одвајање математичких истина од математичких неистина. Овој потрази је потребно да  појам "алгоритма" или "ефективне предвидивост" буду приковани, барем довољно добро за трагање за почетак. Али од самог почетка покушаја Алонза Черча је почела са дебатом која се наставља до данашњег дана. Да ли је појам "ефективне предвидивост" да буде (и) "аксиом или аксиоми" у аксиоматског систему, или (ии) само дефиниција да је "идентификовао" два или више предлога, или (иии) емпиријска хипотеза да се утврди посматрањем природних догађаја, или (ив) или само предлог зарад аргумента (односно "теза").

Период 1930—1952.

У току студирања проблема, Черч и његов студент Стивен Клини увео је појам λ дефинисане функције, и они су били у стању да докажу да се неколико великих класа функција често срећу у теорији бројева λ-дефинисани. Расправа је почела када је Черч предложио да Гедел треба дефинисати "ефективно израчунљиве" функције као λ дефинисане функције. Гедел, међутим, није био убеђен и назвао предлог "темељно не задовољава". Уместо тога, у преписци са Черчом (ца 1934-5), Гедел је предложио акиоматизинг појам "ефективне предвидивости"; Заиста, 1935 у писму Клину, Черч је известио да:

"Његова [Геделов] једина идеја у то време била је да би то било могуће, у смислу ефикасне предвидивост као недефинисаног појма, да наведе скуп аксиома који би отеловљавали општеприхваћена својства овог појма, и да уради нешто на тој основи ".

Али Гедел није понудио даља упутства. На крају, он би предложио своју (примитивну) рекурзију, модификовану од стране Хербранда сугестију, коју је Гедел детаљисао у својим предавањима из 1934 Принстон НЈ(Клини и Росер преписали су белешке). Али "није мислио да две идеје могу на задовољавајући начин бити идентификоване " осим хеуристички ".

Даље, било је неопходно да се идентификују и докаже еквивалентност два појма ефикасне предвидивост. Опремљен ламбда-рачуном и "примитивном" рекурзијом, Стивен Клини уз помоћ Черча и Џ. Б. Росера производи доказе (1933, 1935) да покаже да су два рачуна еквивалентна. Черч накнадно измењује своје методе укључују употребу Хербранд-Гедел рекурзије, а затим је доказао (1936) да је Entscheidungsproblem нерешив: Не постоји уопштен "ефективнан обрачун" (метод, алгоритам) који може да одреди да ли су или не формуле у било којој рекурзији - или ламбда рачуну "важеће" (прецизније: нема методе да се покаже да добро формирана формула има "нормалнан облик").

Много година касније, у писму упућеном Дејвису (ца 1965), Гедел би признао да је "он био, у време ових [1934] предавања, уопште убеђен да његов концепт рекурзије чини све могуће рекурзије". По 1963-4 Гедел би одрекао Хербранд-Гедел рекурзију и λ-рачуницу у корист Тјурингове машине као дефиниције "алгоритма" или "механичког поступка" или "формалног система".

Хипотеза која је довела до природног закона ?: Крајем 1936 Алан Тјурингов рад (такође доказује да је Entscheidungsproblem нерешив) је досрављен усмено, али се још није појавио у штампи. С друге стране, Емил Постов рад 1936 се појавио и био сертификован независно од рада Тјуринговог рада. Пост се снажно не слаже са Черчовом "идентификацијом" ефективне израчунљивости са λ-рачуном и рекурзијом, наводећи:

"Заправо посао је већ урађен од стране Черча и других носи ову идентификацију знатно изван радне фазе хипотезе. Али да прикрије ову идентификацију под дефиницијом ... заслепљује нас на потребу њене непрекидне верификације."

Уместо тога, он сматра појам "ефективне предвидивости" као само "радна хипотеза" која може да се доведе  индукционим образложењем до "природно право", пре него "дефиницију или аксиом". Ову идеју је "оштро" критиковао Черч.

Тако је Пост у свом раду 1936 такође дисконтовао Курт Геделову сугестију Черчу 1934-5 да теза може бити изражена као аксиом или скуп аксиома.

Тјуринг додаје још једну дефиницију, Росер изједначава све три: У само кратком времену, Тјурингов рад 1936-37 "На израчунљивим бројева, са применом у Entscheidungsproblem" се појавио. У њој је навео још један појам "ефективне израчунљивости" са увођењем својих А-машина (сада познате као Тјурингова машина - апстрактан рачунарски модел). У доказу-скици додаје као "Прилог" у свој рад 1936-37 , Тјуринг је показао да су се класе функција дефинисана λ-рачуном и Тјурингова машина поклопиле. Черч је брзо препознао колико је убедљива Тјурингова анализа. У свом прегледу Тјуринговог рада рекао је да је јасно да је Тјурингова идеја "идентификација са ефикасности у обичном (не експлицитно дефинисаном) смислу евидентна одмах".

За неколико година (1939) Тјуринг би предложио, као Черч и Клини пре њега, да је његова формална дефиниција механичке израчунљивости био исправан. Тако, 1939. године, и Черч (1934) и Тјуринг (1939) су индивидуално предложили да њихови "формални системи" буду дефиниције "ефективне предвидивост"; нико није урамио њихове изјаве као тезу.

Росер (1939) је формално идентификовао три појма као дефиниције:

"Све три дефиниције су еквивалентне, тако да није битно која се користи."

Клини предлаже Черчову тезу : Ово је оставило отворен израз једне "тезе" Клинију. У свом раду 1943 Рекурзивни Предикати и квантификатори Клини је предложио своју "ТЕЗУ И":

"Ова хеуристичка чињеница [опште рекурзивне функције су ефикасно израчунате] ... довела је Черча да наведе следећу тезу (22). Иста теза је садржана у Тјуринговом опису рачунских машина (23).

"ТЕЗА И. Свака ефективно израчунљива функција (ефективно одлучив предикат) је опште рекурзивна [Клинијев курзив]

"Од прецизне математичке дефиниције појма ефективно израчунљиве (ефективно одлучиве) је хтео, можемо искористити ову тезу ... као дефиницију тога ..."

"(²²) референце Черча 1936

"(²³) референце Тјуринга 1936–7

Клини иде у белешки да :

"... Та теза има карактер једне хипотезе тачке наглашене од стране Поста и Черча (24). Ако узмемо у обзир и његову тезу обрнутог тврђења као дефиницију, онда је хипотеза је хипотеза о примени математичке теорије развијена из дефиниције. За прихватање хипотезе, постоје, као што смо предложили, прилично уверљиви разлози. "

.. "(24) референце Поста1936 Постова и Черчова формална дефиниција у теорији редних бројева, Фонд, Математика вол 28 (1936) пп.11-21 (види реф #2, Дејвис 1965: 286).

Клинијева Черч-Тјурингова Теза: Неколико година касније (1952) Клини би отворено именовао, бранио, и изражавао две "тезе", а затим их "идентификовао" (показао једнакост) употребом његове Теореме ХХХ:

"Хеуристички докази и други разлози довели су Черча 1936 да предложи следеће тезе.

ТЕЗА И. Свака ефективно израчунљива функција (ефективно одлучив предикат) је опште рекурзивна.

Теорема ХХХ: "Следеће класе парцијалних функција су коекстензивне, тј имају исте чланове: (а) парцијалне рекурзивне функције, (б) израчунљиве функције ...". Тјурингова теза: "Тјурингова теза да свака функција коју би требало природно сматрати за израчунљиву је израчунљива под својом дефиницијом, односно једна од његових машина, је еквивалентна тези Черча од стране Теореме ХХХ."

Каснији развоји

Покушај да се разуме појам "ефективне израчунљивости" је боље водио Робин Ганди (Тјурингов ученик и пријатељ) 1980. да анализира прорачун машине (као супротност људској-израчунљивости поступило од Тјурингове машине). Гандијева радозналост у вези, и анализи, "ћелијског аутомата", "Конвејеве игре живота", "паралелизма" и "кристалног аутомата" га је навело да предложи четири "принципа (или ограничења) ... која су тврдио је, било која машина мора задовољити. " Његов најважнији четврти, "принцип каузалитета" се заснива на "коначној брзини простирања ефеката и сигнала; савремена физика одбацује могућност тренутног деловања на даљину". Од ових принципа и неких додатних ограничења- (1а) доња граница на линеарној димензији било ког дела, (1б) горња граница брзина распростирања (брзина светлости), (2) дискретан напредак машине, и (3) детерминистичко понашање-да производи теорему која "Оно што се може израчунати помоћу уређаја задовољава принципе 1-4 је израчунљиво.".

У касним 1990-им Вилфред Зиг анализирао јњ Тјурингове и Гандијеве појмове "ефективне предвидивост" са намером да "оштрења неформалног појма, формулисање његове опште карактеристике аксиоматски, и истраживању аксиоматског оквира". У свом раду 1997. и 2002. године Зиг представља низ ограничења на понашање једног рачунала- "агент људског рачунарства који наставља механички". Ова ограничења своде на:

• "(Б.1) (Коначности) Постоји фиксно ограничење на броју симболичних конфигурација које рачунало може одмах препознати.
• "(Б.2) (Коначности) Постоји фиксно ограничење на броју унутрашњих стања које могу бити у рачуналу.
• "(Л.1) (Локалитет) Рачунар може променити само елементе посматране симболичке конфигурације.
• "(Л.2) (Локалитет) Рачунар може померити пажњу са једне симболичке конфигурације на другу, али нова посматрана конфигурација мора бити унутар ограничене удаљености од непосредне претходно посматране конфигурације.
• "(Д) (Одлучност) Непосредно препознатљива (суб-) Конфигурација одлучује једнозначно следећи корак израчунавања (и ИД [тренутни опис])"; Другачије речено: "унутрашње стање А рачунало заједно са посматраном конфигурацијом фиксира јединствен следећи корак рачунања и следеће унутрашње стање."

Питање остаје у активној дискусији у оквиру академске заједнице.

Теза као дефиниција

Теза може да се посматра као ништа осим обичне математичке дефиниције. Коментари од Гедела на тему указују на овај став, нпр "основна тачна дефиниција механичке израчунљивости је утврђена ван сваке сумње од стране Тјуринга". Случај за гледање тезе као ништа више од дефиниције је експлицитно створио Роберт И. Соаре у којој се такође тврди да није ништа мање вероватно да ће Тјурингова дефиниција бити тачна него ипсилон-делта дефиниција непрекидне функције.

Успех тезе

Остали формализми (осим рекурзије је λ-рачун, и Тјурингова машина) су предложени за описивање ефикасне предвидивости / израчунљивости. Стивен Клини (1952) додаје на листу функције "Процењиви у систем С1" Курт Гедела 1936, и Емил Постових (1943, 1946) "канонских [такође зване нормалним] система". У 1950. Хао Ванг и Мартин Дејвис у великој мери су поједноставили модел Тјурингове машине са једном траком (види пост-Тјурингову Машине). Марвин Мински је проширио модел на две или више траке и увелико поједностављена трака у "горе-доле шалтерима", које су Мелзак и Ламбек даље еволуирали у оно што је сада познато као модел бројач машине. У касним 1960-им и раним 1970-им истраживачи су проширили модел бројач машине у Регистар машину, блиски рођак са модерним појмом рачунара. Остали модели укључују Комбинацијску логику и Марков алгоритме. Гуревич додаје модел Показивач машине Колмогорова и Успенског (1953, 1958) : "... они су само хтели да ... увере себе да не постоји начин да се продужи појам израчунљиве функције."

Сви ови доприноси укључују доказе да су модели су рачунски еквивалентни Тјуринговој машини; такви модели су, како је речено Тјуринг потпуни. Зато што су сви ови различити покушаји формализовања концепта "ефикасна предвидивост / израчунљивост" дале су еквивалентне резултате, сада се генерално претпоставља да је Черч-Тјурингова теза тачна. У ствари, Гедел (1936) је предложио нешто јаче од овога; он је приметио да постоји нешто "апсолутно" о концепту "Процењиви у С1":

"То може да се покаже да је функција која је израчунљива ['Процењива'] у једном од система Си, или чак у систему трансфинит типа, већ израчунљива [Процењива] у С1. Тако је концепт" за израчунавање "['Процењиви '] у извесном смислу одређеном' апсолутно ', док су практично сви остали познати математички концепти (нпр доказати, дефинисати, итд) зависи доста битно на систему којима су дефинисане "

Неформална употреба у доказима

Докази у теорији израчунљивости често позивају на Черч-Тјурингову тезу на неформалан начин да се успостави израчунљива функција избегавајући (често веома дуго) детаље који ће бити укључени у ригорозан, формални доказ. Да се утврди да је функција израчунљива Тјуринговом машином, обично се сматра довољним да се добије неформалан енглески опис како се функција може ефикасно израчунати, а затим закључити "На основу Черч-Тјурингове тезе" да је функција Тјуринг израчунљива (еквивалентно парцијална рекурзивна).

Дирк ван Дален (у Габаију 2001:284) даје следећи пример зарад илустрације ове неформалне употребе Черч-Тјурингове тезе:

ПРИМЕР: Сваки бесконачни РЕ скуп садржи бесконачан рекурзивни скуп.

Доказ: Нека је бесконачно Ре. Наводимо елементе А ефикасно, n₀, n₁, n₂, n₃, ...

Из овог списка можемо издвојити већу подлисту: стави m₀=n₀, после коначно много корака можемо наћи n_k такво да n_k > m₀, стави m₁=n_k. Понављамо ову процедуру да нађемо m₂ > m₁, итд ово даје ефикасан листинг на подскуп B={m₀,m₁,m₂,...} од А, са имовином m_i < m_i+1.

Тврдња. B је одлучив.Јер, да би тестирали  k у B морамо проверити да ли јеk=m_i за неко i. Како се редослед m_i's  повећава морамо производити највише k+1 елемената листе и поредити их са k. Ако ни један од њих није једнак k, онда k није у B. Док је овај тест ефективан, B је одлучив и, на основу Черчове тезе, рекурзиван.

(Нагласак додат). Да би направио горњи пример потпуно ригорозним, један би морао да пажљиво изгради Тјурингове Машине, или λ-функцију, или пажљиво позвати рекурзије аксиоме, или у најбољем случају, мудро позивати различите теореме теорије израчунљивости. Али пошто теоретичари израчунљивости сматрају да Тјурингова израчунљивост правилно снима оно што се може ефикасно израчунати, и зато ефикасна процедура је написана на енглеском језику за одлучивање у скупу В,  теоретичар израчунљивости прихвата то као доказ да је скуп заиста рекурзиван.

Као правило, Черч-Тјурингова теза да треба применити само да се поједноставе докази у случајевима у којима би писац био у стању да, и очекује да ће читаоци такође да буду у стању да, лако (али не нужно без досаде) производећи ригорозне доказе ако неко од њих захтева.

Варијације

Успех Черч-Тјурингове тезе затражио је да се варијације тезе предложе. На пример, физичка Черч-Тјурингова теза (ФЧТТ) наводи:

"Све физички израчунљиве функције су Тјуринг-израчунљиве"

Черч-Тјурингова теза ништа не говори о ефикасности којом један модел обрачуна може симулирати други. Доказано је, на пример, да само (са више трака) универзална Тјурингова машина трпи фактор логаритамског успоравања за симулирање било које Тјурингове Машине. Такав резултат је показао уопште за произвољан, али и разуман модел израчунљивости. Варијација на Черч-Тјуринговој тези да се бави овим питањем је Теза изводљивости или (Класична) Сложено-теоријски Черч-Тјурингова теза (СТЧТ), која није последица Черча или Тјуринга, већ је реализована постепено у развоју теорије комплексности. У њој се наводи:

"А пробабилистичка Тјурингова машина може ефикасно симулирати било који реалан модел израчунавања."

Реч "ефикасно" овде значи до полиномског смањења времена. Ова теза је првобитно названа Израчунљива Сложено-теоријски Черч-Тјурингова теза од Етана Бернштајна и Умеша Вазиранија (1997). Комплексно-теоријска Черч-Тјурингова теза, онда, претпоставља да ће сви разумни „модели израчунљивости дати исте класе проблема који може да се израчуна на полиномијалном времену. Под претпоставком да пробабилистички полиномијално време (БПП) једнак детерминистичком полиномијалном времену (п), реч 'вероватноће' је опционо у сложено-теоријски Черч-Тјуринговој тези. Слична теза, названа Теза Инваријантности, представио је Цес Ф. Слот и Петер ван Емде Боас. Она каже: "Разумне" машине се могу симулирати међусобно унутар полиномијално ограниченом ваздушном у времену и константнимм горњим фактором  у простору. Теза се првобитно појавио у новинама на СТОЦу'84, који су биле прве новине да покажу да је полиномијално време горњег и константан-простор горњег могу бити истовремено постигнута за симулацију РАМ на Тјуринговој машини.

Ако је БКП приказан да буде строг надскуп БПП, то би поништило Сложено-теоријску Черч-Тјурингову тезу. Другим речима, не би било ефикасних квантних алгоритма који обављају послове који немају ефикасни пробабилистички алгоритми. То не би, међутим, могло да поништи првобитну Черч-Тјурингову тезу, јер квантни рачунар може увек да се симулира Тјуринговом машином, али би поништило класичну Сложено-теоријску Черч-Тјурингову тезу за ефикасност разлога. Сходно томе, Квантно Сложено-теоријска Черч-Тјурингова теза гласи:

"Квантна Тјурингова машина може ефикасно симулирати било који реалан модел израчунљивости."

Јуџин Ебербах и Петер Вегнер тврде да се Черч-Тјурингова теза понекад тумачи превише широко, наводећи "ширу тврдњу да алгоритми управо заузму оно што се може израчунати је неважеће". Они тврде да облици израчунавања нису заробљени од стране тезе су релевантни данас, термини који називају супер Тјуринг израчунљив.

Филозофске импликације

Филозофи су тумачили Черч-Тјурингову тезу да имају импликације за филозофију духа; Међутим, многи од филозофских тумачења тезе укључују основне неспоразуме на изјаве теза. Б Џек Копленд каже да је отворено емпиријско питање да ли постоје стварни детерминистички физички процеси који, на дуже стазе, заобилазе симулацију Тјуринговом машином; Осим тога, он тврди да је отворено емпиријско питање да ли су неки такви процеси укључени у рад људског мозга. Постоје нека важна отворена питања која покривају однос између Черч-Тјурингове тезе и физике, као и могућност хиперизрачунљивости. Када се примени на физици, теза има неколико могућих значења:

1. Универзум је еквивалентан Тјуринговом машином; дакле, израчунљивост не-рекурзивне функције је физички немогуће. Ово је назива Јака Черч-Тјурингова теза и представља темељ дигиталне физике.
2. Универзум није еквивалентан Тјуринговом машином (тј закони физике нису Тјуринг-израчунљиви), али неизрачунљиви физички догађаји нису "харнесејбл" за изградњу хиперрачунара. На пример, универзум у којем физика укључује реалне бројеве, за разлику од израчунљивости реалних бројева, можда спадају у ову категорију. Претпоставка да неизрачунљиви физички догађаји нису "харнесејбл" су изазвали, међутим, предложене рачунарске процесе који користе квантну случајност заједно са рачунарским машинама да сакрију рачунарске кораке универзалне Тјурингове машине са Тјуринг-неизрачунљивим запаљивим обрасцима.
3. Универзум је хиперрачунар, а могуће је изградити физичке уређаје да искористе ову особину и израчунају не-рекурзивне функције. На пример, то је отворено питање да ли су сви Квантномеханички догађаји Тјуринг-израчунљиви, иако је познато да ригорозни модели као што су квантна Тјуринг машина су еквивалентни детерминистичким Тјуринговим машинама. (Они нису нужно ефикасно еквивалентни; види горе.) Џон Лукас и Роџер Пенроуз су сугерисали да људски ум може бити резултат неке врсте квантно-механички појачане, "не-алгоритмическе" израчунљивости, иако нема научних доказа за овај предлог.

Постоје многе друге техничке могућности које спадају изван или између ове три категорије, али они служе да илуструју опсег појма.

Неизрачунљиве функције

Један формално може дефинисати функције које нису израчунљиве. Добро познати пример такве функције је заузетог дабра. Ова функција узима улаз н и враћа највећи број симбола које Тјурингова машина са н стања може да штампа пре заустављања, када се ради без улаза. Проналажење горње границе на прометној функцији даброва је еквивалентна решавању халтинг проблема, проблем познат бити нерешив Тјуринговим машинама. Пошто заузет дабар не може да се израчуна Тјуринговим машинама, Черч-Тјурингова теза каже да ова функција не могу бити ефикасно израчунљива било којом методом.

Неколико рачунарских модела омогућавају израчунавање (Черч-Тјуринг) неизрачунљивих функција. Они су познати као хиперрачунари. Марко Бургин тврди да супер рекурзивни алгоритми, као што су индуктивне Тјурингове машине оповргну Черч-Тјурингову тезу. Његов аргумент почива на дефиницији алгоритма шире од обичне, тако да неизрачунљиве функције добијене из неких индуктивних Тјуринг машина се зову израчунљиве. Ово тумачење Черч-Тјурингове тезе разликује се од тумачења обично прихваћених у теорији израчунљивости, горе наведено. Аргумент да су супер рекурзивни алгоритми заиста алгорими у смислу Черч-Тјурингове тезе није нашао широко прихватање у Израчунљивој истраживачкој заједници.

Др Селим Г Акл са Универзитета Квинс (Школа рачунања) оспорава да је Черч-Тјурингова теза доказиво нетачно заснована на низу функција које су израчунљиве али генерално сматра да буду неизрачунљиве.

Види још

• Апстрактна машина
• Черчова теза у конструктивној математици
• Логика израчунљивости
• Теорија израчунљивости
• Одлучивост
• Историја Черч-Тјурингове тезе
• Хиперрачунар
• Модел израчунљивости
• Супер рекурзивни алгоритам
• Черч-Тјуринг-Немачки принцип, који наводи да сваки физички процес може бити симулиран универзалном рачунарском машином
• Стохастика
• Monte Carlo method

Литература

• Barwise, Jon, H. J. Keisler, and K. Kunen, Editors, The Kleene Symposium, 426 pages, North-Holland Publishing Company, Amsterdam. Kleene, Stephen Cole (1980). The Kleene Symposium: Proceedings of the Symposium Held June 18-24, 1978 at Madison, Wisconsin, U.S.A. North-Holland Publishing Company. ISBN 978-0-444-85345-5. 
• Ben-Amram, Amir M. (2005). „The Church-Turing thesis and its look-alikes”. ACM Sigact News. 36 (3): 113—116. S2CID 13566703. doi:10.1145/1086649.1086651. 
• Bernstein, Ethan; Vazirani, Umesh (1997). „Quantum Complexity Theory”. SIAM Journal on Computing. 26 (5): 1411—1473. doi:10.1137/S0097539796300921. .
• „Algorithms: A Quest for Absolute Definitions” (PDF). октобар 2003: 195—225. CS1 одржавање: Формат датума (веза)
• Burgin, Mark (2005). Super-recursive algorithms: Monographs in computer science. Springer. ISBN 978-0-387-95569-8. 
• Church, Alonzo (1932). „A Set of Postulates for the Foundation of Logic”. Annals of Mathematics. 33 (2): 346—366. JSTOR 1968337. doi:10.2307/1968337. 
• Church, Alonzo (1936). „An Unsolvable Problem of Elementary Number Theory”. American Journal of Mathematics. 58 (58): 345—363. JSTOR 2371045. doi:10.2307/2371045. 
• Church, Alonzo (1936). „A Note on the Entscheidungsproblem”. The Journal of Symbolic Logic. 1 (1): 40—41. JSTOR 2269326. S2CID 42323521. doi:10.2307/2269326. 
• Church, Alonzo (1937). „Reviewed work: On Computable Numbers, with an Application to the Entscheidungsproblem, A. M. Turing”. The Journal of Symbolic Logic. 2 (1): 42—43. JSTOR 2268810. S2CID 73712. doi:10.2307/2268810. 
• Church, Alonzo (1941). The Calculi of Lambda-Conversion. Princeton: Princeton University Press. .
• Cooper, S. B.; Odifreddi, P. (2003). "Incomputability in Nature". In S. B. Cooper & S. S. Goncharov. Computability and Models: Perspectives East and West. Kluwer Academic/Plenum Publishers. стр. 137–160.
• Davis, Martin, ed (1965). The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions. New York: Raven Press. CS1 одржавање: Вишеструка имена: списак аутора (веза)CS1 одржавање: Текст вишка: списак аутора (веза). Includes original papers by Gödel, Church, Turing, Rosser, Kleene, and Post mentioned in this section.
• Eberbach, E.; Wegner, P. (октобар 2003). „Beyond Turing Machines”. Bulletin of the European Association for Theoretical Computer Science. 81: 279—304. CS1 одржавање: Вишеструка имена: списак аутора (веза)CS1 одржавање: Формат датума (веза)
• Gabbay, D.M. (2001). Handbook of Philosophical Logic. 1 (2nd изд.). 
• Gandy, Robin (1980). "Church's Thesis and the Principles for Mechanisms". In H.J. Barwise, H.J. Keisler, and K. Kunen. The Kleene Symposium. North-Holland Publishing Company. стр. 123–148.
• Gandy, Robin; Rolf Herken, ed (1995). The universal Turing Machine: A Half-Century Survey. New York: Wien Springer–Verlag. ISBN 978-3-211-82637-9. CS1 одржавање: Текст вишка: списак аутора (веза)
• Gödel, Kurt (1965) [1934]. "On Undecidable Propositions of Formal Mathematical Systems". In Davis, M. The Undecidable. Kleene and Rosser (lecture note-takers); Institute for Advanced Study (lecture sponsor). New York: Raven Press.
• Gödel, Kurt (1936). On The Length of Proofs.  Ergenbnisse eines mathematishen Kolloquiums (in German) (Heft) (7): 23–24. Cited by Kleene (1952) as "Über die Lāange von Beweisen", in Ergebnisse eines math. Koll, etc.
• Gurevich, Yuri (јун 1988). „On Kolmogorov Machines and Related Issues”. Bulletin of European Association for Theoretical Computer Science. 35: 71—82. CS1 одржавање: Формат датума (веза)
• „Microsoft Research – Emerging Technology, Computer, and Software Research” (PDF). 
• Gurevich, Yuri (2000). „Sequential abstract-state machines capture sequential algorithms”. ACM Transactions on Computational Logic. 1 (1): 77—111. S2CID 2031696. doi:10.1145/343369.343384. 
• Herbrand, Jacques (1932). „Sur la non-contradiction de l'arithmétique”. Journal fur die reine und angewandte Mathematik. 166: 1—8. 
• Hofstadter, Douglas R.. "Chapter XVII: Church, Turing, Tarski, and Others". Gödel, Escher, Bach: an Eternal Golden Braid.
• Kleene, S. C. (1935). „A Theory of Positive Integers in Formal Logic. Part I”. American Journal of Mathematics. 57 (1): 153—173. JSTOR 2372027. doi:10.2307/2372027. 
• Kleene, S. C. (1936). „λ-definability and recursiveness”. Duke Mathematical Journal. 2 (2). doi:10.1215/s0012-7094-36-00227-2. 
• Kleene, S. C. (1943). „Recursive Predicates and Quantifiers”. Transactions of the American Mathematical Society. 54 (1): 41—73. JSTOR 1990131. doi:10.2307/1990131. 
• Kleene, Stephen Cole (1952). Introduction to Metamathematics. . North-Holland. OCLC 523942.
• Knuth, Donald (1973). The Art of Computer Programming. . 1/Fundamental Algorithms (2nd ed.). Addison–Wesley.
• Kugel, Peter (новембар 2005). „Communications of the ACM”. It's time to think outside the computational box. CS1 одржавање: Формат датума (веза) 48  (11):.
• Lewis, H.R.; Papadimitriou, C.H. (1998). Elements of the Theory of Computation. CS1 одржавање: Вишеструка имена: списак аутора (веза). Upper Saddle River, NJ, USA: Prentice-Hall.
• Manna, Zohar (2003) [1974]. Mathematical Theory of Computation. Dover. ISBN 978-0-486-43238-0. 
• Markov, A.A. (1960) [1954]. "The Theory of Algorithms". „American Mathematical Society Translations”. American Mathematical Society Translations. 2 (15): 1—14. 1960. .
• Olszewski, Adam (2006). Church's Thesis After 70 Years. .
• Pour-El, M.B.; Richards, J.I. (1989). Computability in Analysis and Physics. CS1 одржавање: Вишеструка имена: списак аутора (веза). Springer Verlag.
• Rosser, Barkley (1939). „An Informal Exposition of Proofs of Gödel's Theorems and Church's Theorem”. The Journal of Symbolic Logic. 4 (2): 53—60. JSTOR 2269059. S2CID 39499392. doi:10.2307/2269059. 
• Sieg, Wilfried; Sommer, Richard; Talcott, Carolyn, ур. (16. 8. 2002). Reflections on the Foundations of Mathematics: Essays in Honor of Solomon Feferman: Lecture Notes in Logic 15. Taylor & Francis. ISBN 978-1-56881-169-7. CS1 одржавање: Формат датума (веза)
• Soare, Robert (1996). „Computability and Recursion”. Bulletin of Symbolic Logic. 2: 284—321. 
• Syropoulos, Apostolos (2008). Hypercomputation: Computing Beyond the Church-Turing Barrier. Springer. ISBN 978-0-387-30886-9. 
• Turing, A. M. (1937). „On Computable Numbers, with an Application to the Entscheidungsproblem”. Proceedings of the London Mathematical Society: 230—265. S2CID 73712. doi:10.1112/plms/s2-42.1.230. 
• Turing, A. M. (1938). „On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction”. Proceedings of the London Mathematical Society: 544—546. doi:10.1112/plms/s2-43.6.544. . (See also: Davis 1965:115ff)

Спољашње везе

• The Church–Turing Thesis entry by B. Jack Copeland in the Stanford Encyclopedia of Philosophy.
• Computation in Physical Systems —a comprehensive philosophical treatment of relevant issues
• Transcendental idealism and Post’s variant of the Church-Turing thesis —EGTheory blog